With the growth of activity involving transactions among large numbers of parties via large networks such as the Internet, many applications have developed in which a large number of clients may wish to obtain a result based on inputs provided by each of the clients. For example, an online auction may be set up in which a large number of users may submit bids for individual items, such that none of the bidding users has any knowledge of any others of the bidding users. Each bidding user may have an interest in winning the auction for the lowest possible bid that exceeds all other bidding users' bids. All bidding users may receive a result indicating the winning bid at the end of the auction. As an example, at the end of an auction, a bidding user may wish to contest the result, as the bidding user may know that their bid was higher than the result provided to them. However, all bidding users may wish to remain anonymous to all other bidding users, and may wish to withhold certain information from a service provider that may process the auction.
Secure multiparty computation (SMC) generally may involve a cryptographic computation of functions, such that the input of the parties may remain private (i.e., confidential with that party). Only the result (or results) may be revealed to the parties and what may be inferred from one party's input and output may be implicitly revealed. Conventional SMC may assume that a subset (e.g., a majority) of the parties are honest and complete the protocol whereas the other parties may be malicious and may eventually drop out of the protocol.
Distributed algorithmic mechanism design (DAMD) may involve computing functions, such that a result may be compatible with the utility of the collaborating agents and the computation may be efficient in computation and communication complexity. In some applications, it may be desirable for agents to keep their input private, i.e., it may be in their best interest to not reveal their input.
However, it may be difficult to prevent collusion among agents that may lead to invalid results of certain types of computations. Thus, it may be desirable to provide techniques for multiparty secure computation.